Thường Vạn Toàn sinh tháng 1 năm 1949 ở trấn Thạch Kiều, thành phố Nam Dương, tỉnh Hà Nam, gia nhập quân ngũ tháng 3 năm 1968 và vào Đảng Cộng sản Trung Quốc tháng 11 năm 1968. Ông từng tham gia cuộc chiến tranh biên giới Việt-Trung[1]

Tháng 10 năm 1994, ông được bổ nhiệm làm Tham mưu trưởng Tập đoàn quân số 47. Năm 2000, ông được bổ nhiệm sau làm Tư lệnh Tập đoàn quân sau 2 năm làm chủ nhiệm tại Đại học Quốc phòng. Sau đó, ông lần lượt đảm nhiệm các chức vụ Tham mưu trưởng Quân khu Lan Châu, Tham mưu trưởng Quân khu Bắc Kinh, Tư lệnh Quân khu Thẩm Dương.Năm 2007, ông được chính Chủ tịch Hồ Cẩm Đào bổ nhiệm làm Chủ nhiệm Tổng cục Trang bị và được bầu vào Quân ủy Trung ương Trung Quốc. Ông cũng chính đã chỉ huy 3 lần phóng tàu Thần Châu 7, 8, 9 thành công.

Tháng 11 năm 2012, ông tiếp tục được bầu vào Quân ủy Trung ương Trung Quốc nhưng không trở thành Phó chủ tịch Quân ủy như dự đoán. Ngày 16 tháng 3 năm 2013, Quốc hội Trung Quốc đã phê chuẩn Thường Vạn Toàn, người chịu trách nhiệm giám sát chương trình vũ trụ của Trung Quốc, vào vị trí Bộ trưởng Bộ Quốc phòng Trung Quốc.[2] Việc này được nhiều người coi là ông bị thất sủng, bởi với vị trí Chủ nhiệm Tổng cục Trang bị, ông là ứng viên lớn nhất cho ghế Phó Chủ tịch Quân ủy Trung ương Trung Quốc.

Ông được phong quân hàm Thiếu tướng năm 1997, Trung tướng năm 2003 và Thượng tướng năm 2007.